In a number of telecommunication applications including radio and optical communications, forward-error correction (FEC) codes, such as low-density parity-check (LDPC) codes, have been used to realize reliable data communications under noisy channels. In particular, LDPC codes have achieved excellent performance near the theoretical Shannon limit in practice. FEC codes are decoded with various implementations of belief propagation (BP) decoding methods. For example, different variants of sum-product methods (SP), e.g., a min-sum (MS) method, a delta-min (DM) method, a modified min-sum (MMS) method, and a shifted min-sum (SMS) method, use the framework of the BP decoding. The BP decoding uses an iterative message-passing to propagate soft-decision belief messages over a Tanner graph for correcting potential errors occurred during the data communications over noisy channels.
Most FEC codes are characterized by a parity-check matrix (PCM) H containing some nonzero entries, which come from the Galois field of GF(2q), where q is a positive integer called field order. These FEC codes can be represented by a bipartite graph called Tanner graph, which is more useful representations when carrying out the iterative decoding process. The Tanner graph representation of an LDPC code includes two sets of nodes and edges connecting these nodes. One set of nodes is called variable nodes, representing the bits associated with a codeword. The other set of nodes is called check nodes, representing parity-check constraints on the bits of the codeword. An edge of the graph connects a variable node to a check node only if that particular bit represented by the variable node participates in the parity-check equation represented by the check node. Since PCM for LDPC codes has a small number of nonzero entries, the Tanner graph becomes a sparse graph having a few number of edges. The sparse Tanner graph can provide the possibility of computationally efficient BP decoding.
Different BP decoders iteratively pass the received codewords on the Tanner graph to decode the transmitted codewords. The message passing operations at check nodes require nonlinear functions for the original SP method. There are many versions, such as MS method for the BP decoder, that use message-passing approach to simplify the decoding operations for low-power hardware implementation. In addition, most practical decoder implementations need quantized versions of BP decoding for finite-precision processors, which use a fixed number of bits to represent the belief messages.
A message-passing method can be described by defining an update rule at the variable nodes and an update rule at the check nodes. The variable node update rule and the check node update rule can be denoted as functions used to determine the outgoing messages. For example, initially, all belief messages are set to zero and the variable node receives only the channel likelihood value. The variable node sends this channel likelihood value as its outgoing belief message to all its neighboring check nodes in the first iteration. At the check nodes, the check node update rule is used to determine the outgoing belief messages, and the outgoing belief messages are passed to the variable nodes. At the variable node, the variable node update rule is used to determine the outgoing belief messages, and in this manner messages are iteratively passed between variable nodes and the check nodes until a termination condition is met, e.g., a predefined maximum number of iterations.
Most BP decoders are implemented in the “log-likelihood domain,” and the computation of the update rule requires computation of logarithmic functions. To simplify the computations for finite-precision processors, some quantized BP decoders use look-up tables (LUT) to pre-compute the closest-possible results of such logarithmic functions, see e.g., U.S. Pat. No. 8,458,556, U.S. Pat. No. 7,552,379, and U.S. Pat. No. 7,447,985.
Although the LUT implementations are computationally efficient, the number of quantization levels needs to be sufficiently large in order to keep the degradation due to quantization negligible compared to idealistic floating-point processing. In addition, the bit widths of the LUT output needs to be increased in cascaded structure to obtain intermediate data, and to be truncated when iterating the BP processing. Moreover, the LUT does not work well for different signal-to-noise ratio (SNR) because of the dynamic range of input LLR varies. Accordingly, there is a need to improve both the efficiency and accuracy of LUT implementations for quantized BP decoders.